package com.foxzzz.dynamic.programming;

import java.util.*;

// ?
public class Solution312 {
    public static void main(String[] args) {
        System.out.println(new Solution312().maxCoins1(new int[]{3, 1, 5, 8}));
        System.out.println(new Solution312().maxCoins(new int[]{3, 1, 5, 8}));
    }


    public int maxCoins(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] array = new int[nums.length + 2];
        for (int i = 0; i < nums.length; i++) {
            array[i + 1] = nums[i];
        }
        array[0] = 1;
        array[array.length - 1] = 1;

        return maxCoins(array, 0, array.length - 1, new HashMap<String, Integer>());
    }

    public int maxCoins(int[] array, int start, int end, HashMap<String, Integer> map) {
        int max = 0;
        if (map.get(start + "-" + end) != null)
            return map.get(start + "-" + end);
        for (int i = start + 1; i < end; i++) {
            /// error max = Math.max(max, array[i + 1] * array[i] * array[i - 1] + maxCoins(array, start, i) + maxCoins(array, i, end));
            max = Math.max(max, array[start] * array[i] * array[end] + maxCoins(array, start, i,map) + maxCoins(array, i, end,map));
        }
        map.put(start + "-" + end,max);
        return max;
    }


    //回溯超时

    public int maxCoins1(int[] nums) {
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            list.add(nums[i]);
        }
        Map<String, Integer> map = new HashMap<>();
        List<Integer> results = new ArrayList<>();
        max(results, list, 0);
        int max = Integer.MIN_VALUE;
        for (Integer result : results) {
            max = max > result ? max : result;
        }
        return max;

    }

    public void max(List<Integer> results, List<Integer> list, int result) {
        if (list.size() == 0) {

            results.add(result);
            return;
        }
        for (int i = 0; i < list.size(); i++) {
            int left = i - 1 < 0 ? 1 : list.get(i - 1);
            int right = i + 1 == list.size() ? 1 : list.get(i + 1);
            int self = list.get(i);
            result = result + left * self * right;
            list.remove(i);
            max(results, list, result);
            result = result - left * self * right;
            list.add(i, self);
        }
    }
}
